package 回溯;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 字符串的排列.java
 * @Description TODO
 * @createTime 2020年11月04日 14:32:00
 * 输入一个字符串，打印出该字符串中字符的所有排列。
 *
 *  
 *
 * 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
 *
 *  
 *
 * 示例:
 *
 * 输入：s = "abc"
 * 输出：["abc","acb","bac","bca","cab","cba"]
 *
 *
 * 总结：字符串问题
 * 去重用Set
 */
public class 字符串的排列 {
    public static void main(String[] args) {
        Solution solution=new Solution();
        String[] abcs = solution.permutation("aac");
        System.out. println(Arrays.toString(abcs));
    }
    static class Solution {
        HashSet<String> res=new HashSet<>();
        public String[] permutation(String s) {
            boolean[] used=new boolean[s.length()];
            back(s,"",used);
            String[] temp=new String[res.size()];

            return res.toArray(temp);
        }

        private void back(String s, String a, boolean[] used) {
            if(a.length()==s.length()){
                res.add(a);
                return;
            }
            for(int i=0;i<s.length();i++){
                if(used[i]){
                    continue;
                }
                //这么写是错误的
               // a+=s.charAt(i);
                used[i]=true;

                back(s,a+s.charAt(i),used);
                used[i]=false;
            }
        }
    }
}
